In a communications network, switching devices (“switches”) receive data at one of a set of input interfaces and forward the data on to one or more of a set of output interfaces. Users typically require that such switching devices operate as quickly as possible in order to maintain a high data rate. Switches are typically data link layer devices that enable multiple physical network (e.g., local area network (LAN) or wide area network (WAN)) segments to be interconnected into a single larger network. Switches forward and flood data traffic based on, for example, MAC addresses. In the most general sense, these types of networks transport data in the form of frames. A frame is a logical grouping of information sent as a data link layer unit over a transmission medium. Frames typically include header and/or trailer information used, for example, for routing, synchronization, and error control. The header and/or trailer information surrounds user data contained in the unit. The terms cell, datagram, message, packet and segment are also used to describe logical information groupings at various layers of the OSI reference model and in various technology circles. As used herein, the term “frame” should be understood in its broadest sense, and can encompass other terms such as cell, datagram, message, packet and segment.
FIG. 1 illustrates a simplified block diagram of a switching network 100, such as a LAN switching network. In this example, the switch includes switching fabric 110 and multiple line cards 120 and 130. The switch thus connects various network devices 122, 124, 132, and 134 to each other through switching fabric 110 via line cards 120 and 130. Network devices 122, 124, 132, and 134 can, in general, include a variety of different devices including computer systems, output devices, storage devices, communications devices, or other network components such as routers, other switches, and even other networks.
It will be noted that the variable identifier “N” is used in FIG. 1 (and in other parts of this application) to more simply designate the final element (e.g., line card N 130) of a series of related or similar elements. The repeated use of such variable identifiers is not meant to imply a correlation between the sizes of such series of elements, although such correlation may exist. The use of such variable identifiers does not require that each series of elements has the same number of elements as another series delimited by the same variable identifier. Rather, in each instance of use, the variable identified by “N” may hold the same or a different value than other instances of the same variable identifier.
Switching network 100 can employ one or more of a variety of different communication protocols enabling data communication between network devices. Line cards 120 and 130 generally take the form of an I/O interface card that typically performs data frame analysis as part of the switching process. Switching fabric 110 can also be implemented in a variety of ways. Three common types of switching fabrics are single-bus architectures, shared-memory architectures, and crossbars. Single-bus switching fabric architectures use a central fabric element within the switch to which all the ports of the switch communicate. Each port arbitrates for access to this fabric because there is one central switching element. With shared-memory architectures, a shared memory stores data frames and a high-speed ASIC reads and writes to the memory. Frames come into the architecture, a switching core places them in memory and then queues them to their outbound port. Buffering is internal to the switching fabric in this architecture, and buffers may be either fixed or dynamic. Crossbars use a mesh within the switching fabric to connect all the ports or all the line cards at high speed. Crossbars can be highly efficient for “balanced traffic,” e.g., if port 1 and port 2 are communicating, and port 3 and port 4 are communicating then the crossbar directs those transmissions onto different paths.
One of the key benefits of crossbars is the ability to scale to significantly high bandwidth and throughputs. Consequently, crossbars are a popular type of switching fabric. FIG. 2 illustrates several features of prior art crossbar-based switching schemes. In support of the crossbar 200, switching fabric 110 includes one or more input buffers 210 and one or more output buffers 220. In a typical implementation there are input and output buffers for each port in the switching fabric. Consequently, input and output buffers can be associated with particular line cards by virtue of the buffers' association with a particular port. In this example, data frames to be transferred from line card l 120 to line card N 130 are first queued in queue 240 of line card 120. Queue 240 can be implemented as a first in first out (FIFO) buffer using a variety of memory structures as is well known in the art. Once a data frame is ready for transmission, it is serialized and transmitted across a serial channel where it is received by input buffer 210 of switching fabric 110. The data frame is transmitted across crossbar 200 to the output buffer corresponding to the appropriate port of exit, in this case output buffer 220. From output buffer 220, the data frame is serialized and transmitted to the line card corresponding to output buffer 220 port, in this case line card N 130. The data is typically received in a queue such as queue 250.
Since output buffer 220 can in general receive data from any input port attached to switching fabric 110, i.e., not just the port associated with input buffer 210 and line card l 120, congestion problems can occur. Accordingly, it is desirable to have a switching fabric architecture that reduces the likelihood of congestion at its output buffers and accomplishes this goal with minimal impact on the switching fabric's bandwidth, throughput, and complexity.